#include <iostream>
#include <vector>
#include <algorithm>
#include <sys/time.h>

using namespace std;

void combSum(vector<int> &candidates,int target ,vector<int> &cur,vector<vector<int> > & res,int begin) {
  if(target == 0) {
    res.push_back(cur);
    return ;
  } else {
    for( int i = begin; i<candidates.size() && target>=candidates.at(i) ; ++i ) {
      cur.push_back( candidates.at(i) );
      combSum( candidates, target-candidates.at(i), cur, res, i+1);
      cur.pop_back();

    }
  }
}




vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
  vector<vector<int>> ret;
  int m = candidates.size(); 
  if(m<1)
    return ret;

  std::sort( candidates.begin(), candidates.end() );
  vector<int> cur;
  combSum(candidates,target,cur,ret,0);
  // 去重  
  vector<vector<int> >::iterator end = ret.end();    
  sort(ret.begin(), end, less<vector<int> >());  
  vector<vector<int> >::iterator new_end = unique(ret.begin(), ret.end());  
  ret.erase(new_end, end);  


  return ret;



}



int main(int argc,char *argv[])
{
  vector<int> comb={10,1,2,7,6,1,5};
  int target = 8;
  vector<vector<int>> ret;



  struct  timeval    tv1,tv2;
  struct  timezone   tz;
  int time1 = gettimeofday(&tv1,&tz);

  //func();
  //
  ret = combinationSum(comb,target);

  for(auto i : ret) {
    for(auto j : i) {
      cout<<j<<",";
    }
    cout<<endl;
  }

  int time2 = gettimeofday(&tv2,&tz);
  cout << "time consuming(local machine/leetcode server):"<<endl
    <<"leetcode server time consuming should be less than 500ms"<<endl
    << tv2.tv_usec - tv1.tv_usec <<"us/"<<0.11*( tv2.tv_usec - tv1.tv_usec )<<"ms"<< endl;



  return 0;
}
